import java.util.TreeMap;

public class Solution220 {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeMap<Long,Integer> treeMap=new TreeMap<>();
        for (int i=0;i<nums.length;i++){
            if (i>k){
                treeMap.put((long)nums[i-k-1],treeMap.get((long)nums[i-k-1])-1);
                if (treeMap.get((long)nums[i-k-1])==0){
                    treeMap.remove((long)nums[i-k-1]);
                }
            }
            Long integer=treeMap.ceilingKey((long)nums[i]-t);
            if (integer!=null && integer-t<=(long)nums[i]){
                return true;
            }
            treeMap.put((long)nums[i],treeMap.getOrDefault((long)nums[i],0)+1);
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new Solution220().containsNearbyAlmostDuplicate(new int[]{1,5,9,1,5,9},2,3));
    }
}
